package LeetCode;

import java.util.ArrayList;
import java.util.Scanner;

public class LC_022_GenerateParentheses {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            ArrayList<String> res = generateParenthesis(n);
            System.out.println(res.toString());
        }
    }

    private static ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        String item = "";

        if (n <= 0)
            return res;

        dfs(res, item, n, n);
        return res;
    }

    private static void dfs(ArrayList<String> res, String item, int left, int right) {
        if (left > right)
            return;

        if (left == 0 && right == 0) {
            res.add(item);
            return;
        }

        if (left > 0)
            dfs(res, item + '(', left - 1, right);

        if (right > 0)
            dfs(res, item + ')', left, right - 1);
    }
}
